package com.vint.leetcode;


/*
 * 1. done
 * 2. easy
 * 3.
 */
public class Leetcode34 {
	public int[] searchRange(int[] nums, int target) {
		int start = searchLeft(nums, 0, nums.length - 1, target);
		int end = searchRight(nums, 0, nums.length - 1, target);
		return new int[]{start, end};
	}

	public int searchLeft(int[] nums, int start, int end, int target) {
		if(end<start)return -1;
		if(end==start){
			if(nums[start] == target){
				return start;
			}else {
				return -1;
			}
		}
		int mid = (start + end) / 2;
		if(nums[mid] == target){
			int left = searchLeft(nums, start, mid -1 ,target);
			if(left == -1){
				return mid;
			} else{
				return left;
			}
		} else if(nums[mid] > target){
			return searchLeft(nums, start, mid -1, target);
		} else {
			return searchLeft(nums, mid +1, end, target);
		}
	}
	public int searchRight(int[] nums, int start, int end, int target) {
		if(end<start)return -1;
		if(end==start){
			if(nums[start] == target){
				return start;
			}else {
				return -1;
			}
		}
		int left = -1;
		int mid = (start + end) / 2;
		if(nums[mid] == target){
			int right = searchRight(nums, mid + 1, end, target);
			if(right == -1){
				return mid;
			} else{
				return right;
			}
		} else if(nums[mid] > target){
			return searchRight(nums, start, mid -1, target);
		} else {
			return searchRight(nums, mid +1, end, target);
		}
	}
}


